
#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h> // for longjmp, setjmp etc..
#include <signal.h> // for signal handlers
#include <unistd.h> // for ualarm
#include <assert.h>
#include <string.h>
#include <sched.h>
#include "user_threads.h"
#include "common.h"

#if 0
#define PRK(...) write(__VA_ARGS__)
#else
#define PRK(...)  {}
#endif

#define voodoo(...) {} //NOAM: fix


#ifndef JB_SP
#define JB_SP 4
#endif

#define UTHREAD_ZOMBIE_JOINED 3
#define UTHREAD_DELETED 4

/* Global variables */
uthread current;
uthread all_threads[UTHREAD_MAX_THREADS]; //NOAM: array of pointers to uthread
uthread_id next_open;

/* Declerations of header functions within the code */
void uthread_exit(int retval);

/* Decrlerations of static functions within the code */
static void reset_alarm();

static void sig_handler(int signum);
static int context_switch(uthread prev, uthread next);
void do_exit(uthread thread, int retval);
static int get_new_id();
static uthread get_next_running(uthread prev);
static void garbage_collector();
void deactivate_thread(uthread thread);

void find_next_and_cs(uthread thread);
void kill_all();

/*void assert_arr(int x) {
	return;
	int i = 0;
	i=0;
	while (i < 10) {
		if (!p->next) {
			printf("1error i=%d\n",i);
			goto bug;
		}
		if (!p->next) {
			printf("2error i=%d\n",i);
			goto bug;
		}
		if (!p->prev) {
			printf("3error i=%d\n",i);
			goto bug;
		}
		if (p->next->prev != p) {
			printf("4error i=%d\n",i);
			goto bug;
		}
		if (p->prev->next != p) {
			printf("5error i=%d\n",i);
			goto bug;
		}
		i++;
		p = p->next;
	}
	return;
bug:
	printf("BUG X: %d\n",x);
	printf("&r: 0x%x, r.n: 0x%x, r.n.n: 0x%x, r.n.n.n: 0x%x\n",&running,running.next,running.next->next,running.next->next->next);
	printf("p->prev: 0x%x, p: 0x%x, p->next: 0x%x\n",p->prev,p->next);
	printf("p->prev->next: 0x%x, p->next->prev: 0x%x\n",p->prev->next,p->next->prev);
	exit(11);
	for(;;);
} */


int uthread_init() {
	uthread head = malloc(sizeof(*head));
	if (!head) {
		return UTHREAD_FAIL;
	}
	memset(all_threads,0,sizeof(all_threads));
	/* init global queues */
	head->id = 0;
	head->magic = 123456;
	head->magic2 = 7890;
	head->join_by = -1;
	head->join_to = -1;
	head->state = UTHREAD_RUNNING;
	head->prio = UTHREAD_MIN_PRIO;
	head->ret_value = UTHREAD_INVALID;
	head->args = NULL;
	head->func = NULL;
	head->ret_value_joined = NULL;
	if (uthread_mutex_init_general() != MUTEX_SUCCESS) {
		free(head);
		all_threads[0] = NULL;
		return UTHREAD_FAIL;
	}
	head->locked_mutexes = thread_list_create();
	if (!head->locked_mutexes) {
		free(head);
		all_threads[0]=NULL;
		return UTHREAD_FAIL;
	}
	head->mutex_waiting_on = NULL;
	current = head;
	all_threads[0] = current;
	activate_thread(head);
	is_uthread_initialized = 1;
	atexit(&kill_all);
	signal(SIGALRM,sig_handler); /* NOAM: moved the signal cmd after i finish init */
	ualarm(UTHREAD_TIME_SLICE * current->prio,0);
	return UTHREAD_SUCCESS;
}
uthread_id uthread_self() {
	return current->id;
}
//void start_routine_wrapper() {
//    int retval=(current->func)(current->args);
//	uthread_exit(retval);
//}
uthread_id uthread_create(UTHREAD_START_ROUTINE start_routine, void* arg,
                          int prio) {
	uthread_id new_id;
	uthread new_thread;
	lock_alarm();
	new_id = get_new_id();
	new_thread = malloc(sizeof(*new_thread));
	if (new_id == UTHREAD_FAIL ||
						prio < UTHREAD_MIN_PRIO || prio > UTHREAD_MAX_PRIO) {
		goto out;
	}
//	printf("trying to create id %d\n",new_id);
	if (!new_thread) {
		goto out_unlock;
	}
	all_threads[new_id] = new_thread;
	new_thread->id = new_id;
	new_thread->prio = prio;
	new_thread->join_by = -1;
	new_thread->join_to = -1;
	new_thread->ret_value = UTHREAD_INVALID;
	new_thread->magic = 123456;
	new_thread->magic2 = 7890;
	new_thread->args = arg;
	new_thread->func = start_routine;
	new_thread->ret_value_joined = NULL;
	new_thread->stack = malloc(UTHREAD_DEF_STACK_SIZE);
	if (!new_thread->stack) {
		free(new_thread);
		all_threads[new_id] = NULL;
		new_id = UTHREAD_FAIL;
		goto out_unlock;
	}
	new_thread->locked_mutexes = thread_list_create();
	if (!new_thread->locked_mutexes) {
		free(new_thread);
		free(new_thread->stack);
		all_threads[new_id] = NULL;
		new_id = UTHREAD_FAIL;
		goto out_unlock;
	}
	new_thread->mutex_waiting_on = NULL;
	char c[200];
	int ret;
	if (new_id == 2) {
		ret = sprintf(c,"### stack pointer for 2: 0x%x\n",new_thread->stack);
		PRK(1,c,ret);
	}
	activate_thread(new_thread);

	if (sigsetjmp(new_thread->current_instruction,1)) {
		/* welcome back! I missed you XOXO */
//		printf("first run after my creation. my id: %d\n",current->id);
//		ualarm(UTHREAD_TIME_SLICE * current->prio,0);
		reset_alarm();
		uthread_exit((current->func)(current->args));
	}
	/* first time of the set jump */
	new_thread->current_instruction->__jmpbuf[JB_BP] = ((long int)(new_thread->stack)) + UTHREAD_DEF_STACK_SIZE - 4;
	new_thread->current_instruction->__jmpbuf[JB_SP] = ((long int)(new_thread->stack)) + UTHREAD_DEF_STACK_SIZE - 16;	
//	new_thread->current_instruction->__jmpbuf[JB_PC] = (int) start_routine_wrapper;
//	printf("a\n");
out_unlock:
	unlock_alarm();
out:
//	printf("b: %d\n", new_id);
	return new_id;
}

void uthread_exit(int retval) {
//	printf("uthread_exit, ID: %d\n",current->id);
	lock_alarm();
	do_exit(current, retval);
	find_next_and_cs(current);

}
int uthread_cancel(uthread_id th) {
	lock_alarm();
	if (!all_threads[th]) {
		unlock_alarm();
		return UTHREAD_INVALID;
	}
	else if (!(all_threads[th]->state==UTHREAD_RUNNING || all_threads[th]->state==UTHREAD_SUSPENDED)) {
		unlock_alarm();
		return UTHREAD_FAIL;
	}
	do_exit(all_threads[th],UTHREAD_CANCELLED);
	unlock_alarm();
	return UTHREAD_SUCCESS;
	//NOAM: when should i return UTHREAD_ERROR? why? a deadlock of some sort?
	//BORIS: zombie or zombie_joined. see else if above.
}
int uthread_join(uthread_id th, int* thread_return) {
	int retval;
	char cc[60]; int d;
	assert(current->join_to < 0); /* if it's >=0, then thread should be asleep */
	lock_alarm();
	if (th < 0 || th > UTHREAD_MAX_THREADS || !all_threads[th]) {
		retval = UTHREAD_INVALID;
		thread_return = NULL;
		goto out_unlock;
	}
	if (current->id == th ||
		all_threads[th]->join_by > -1 ||
		all_threads[th]->state == UTHREAD_ZOMBIE_JOINED ||
		all_threads[th]->state == UTHREAD_DELETED) {
		/* Trying to join an already joined */
		retval = UTHREAD_FAIL;
		thread_return = NULL;
		goto out_unlock;
	}

	d=sprintf(cc,"Thread %d joined %d. Thread %d is %d\n",current->id,th,th,all_threads[th]->state);
	PRK(1,cc,d);
	if (all_threads[th]->state == UTHREAD_ZOMBIE) {
		/* NOAM: trying to join a zombie thread
		 * th is zombie, because (according to Eyal (TA) on 8/1/2012) a thread
		 * should remain zombie iff  it does not have a father (joining him)
		 * and has a son that has not finished yet.
		 */
		all_threads[th]->state = UTHREAD_ZOMBIE_JOINED;
		if (all_threads[th]->join_to < 0) {
			/* th was a zombie because it had no sons and was waiting for a parent.
			 * now it has a parent, so we can finnally kill th.
			 */
			all_threads[th]->state=UTHREAD_DELETED;
		}
		if (thread_return) {
			*thread_return = all_threads[th]->ret_value;
		}
		goto out_success;
	}


	current->join_to = th;
	all_threads[th]->join_by = current->id;
	all_threads[th]->ret_value_joined = thread_return;
	deactivate_thread_and_cs(current);
	/* here returned from the join */
out_success:
	retval = UTHREAD_SUCCESS;

out_unlock:
	unlock_alarm();
	return retval;
}

void uthread_yield() {
	kill(getpid(),SIGALRM);
}

void kill_all() {
	int i;
	for (i = 1; i< UTHREAD_MAX_THREADS; i++) {
		if (all_threads[i]) {
			all_threads[i]->state = UTHREAD_DELETED;
		}
	}
	garbage_collector();
	voodoo(free mutex list for all_threads[0]);
	free(all_threads[0]);
}

void do_exit(uthread thread, int retval) {
	if (thread->id == 0) {
		exit(retval);
	}
	char cc[60]; int d;
	d=sprintf(cc,"Killed thread %d. Reason=%d\n",thread->id,retval);
	PRK(1,cc,d);
	PRK(1,"moo?\n",5);
	thread->state = UTHREAD_ZOMBIE;
	thread->ret_value = retval;
	if (thread->join_by > -1) {
		d=sprintf(cc,"needs to handle join_by=%d\n",thread->join_by);
		PRK(1,cc,d);
		thread->state = UTHREAD_ZOMBIE_JOINED; // thread has join_by and therefore must be UTHREAD_ZOMBIE_JOINED or UTHREAD_DELETED
		assert(all_threads[thread->join_by]);
		assert(all_threads[thread->join_by]->state != UTHREAD_RUNNING);
		//if (all_threads[thread->join_by]->state == UTHREAD_SUSPENDED) {
		//	activate_thread(all_threads[thread->join_by]);
		//}
		/*else*/ if (thread->join_to < 0) {
			if (all_threads[thread->join_by]->state == UTHREAD_ZOMBIE_JOINED) {
				int idx = thread->join_by;
				d=sprintf(cc,"Thread joined by %d . Thread %d is %d and joined by %d\n", idx, idx, all_threads[idx]->state, all_threads[idx]->join_by);
				PRK(1,cc,d);
				while (all_threads[idx]->join_by > -1 && all_threads[idx]->state == UTHREAD_ZOMBIE_JOINED) {
					all_threads[idx]->state = UTHREAD_DELETED;
					d=sprintf(cc,"Thread %d marked for deletion1\n", idx);
					PRK(1,cc,d);
					idx = all_threads[idx]->join_by;
				}
				if (all_threads[idx]->state == UTHREAD_ZOMBIE_JOINED) {
					all_threads[idx]->state = UTHREAD_DELETED;
					d=sprintf(cc,"Thread %d marked for deletion2\n", idx);
					PRK(1,cc,d);
				}
				else if (all_threads[idx]->state == UTHREAD_SUSPENDED) {
					activate_thread(all_threads[idx]);
				}
				all_threads[idx]->join_to = -1;
			}
			else if (all_threads[thread->join_by]->state == UTHREAD_SUSPENDED) {
				activate_thread(all_threads[thread->join_by]);
			}
		}

		if (thread->ret_value_joined) {
			*(thread->ret_value_joined) = retval;
		}
		if (thread->join_to < 0) {
			all_threads[thread->join_by]->join_to = -1;
			thread->state = UTHREAD_DELETED;
			thread->join_by = -1;
		}
	}

	d=sprintf(cc,"Thread %d has status %d\n",thread->id,thread->state);
	PRK(1,cc,d);
	
	PRK(1,"foo!\n",5);
	
	//find_next_and_cs(current);
}

void lock_alarm() {
	current->lock_alarm = ualarm(0,0);
	if (current->lock_alarm == 0) {
		current->lock_alarm = 1;
	}
}
void unlock_alarm() {
	ualarm(current->lock_alarm,0);
}
int get_new_id() {
	int i;
	for (i = 0; i<UTHREAD_MAX_THREADS; i++) {
		if (!all_threads[i]) {
			break;
		}
	}
	return i == UTHREAD_MAX_THREADS ? UTHREAD_FAIL : i;
}

//	printf("context_switch... prev=%d next=%d\n", prev->id, next->id);
int context_switch(uthread prev, uthread next) {
	if (prev == next) {
		current = next; /* for safety if for some reason current is not prev */
		goto out;
	}
	if (sigsetjmp(current->current_instruction,1) == 0) {
		/* First time called, need to jump to the next.*/
		current = next;
		siglongjmp(current->current_instruction,68);
	}
	else {
		/* Welcome back! We missed you :D */
	}
	garbage_collector();
out:
	reset_alarm();
	return 0;
}

uthread get_next_running(uthread prev) {

	uthread next = NULL;
	uthread_id idx = (prev->id + 1) % UTHREAD_MAX_THREADS;
	if (prev->state == UTHREAD_RUNNING) {
		next = prev;
	}
	while (idx != prev->id) {
		if (all_threads[idx] && all_threads[idx]->state == UTHREAD_RUNNING) {
			next = all_threads[idx];
			break;
		}
		idx = (idx + 1) % UTHREAD_MAX_THREADS;
	}
	return next;
}

void sig_handler(int signum) {
	uthread prev,next;
	int idx, prev_found;
	uthread next_test;
//	char a[200],b[50],c[50],d[50];
//	int ret;
//	PRK(1,"signal!\n",8);

	prev = current;
	prev_found=0;
	idx = 0;
	while (1) {
		if (all_threads[idx] == prev && !prev_found) {
			prev_found=1;
		}
		else if (prev_found && all_threads[idx] && (all_threads[idx]->state == UTHREAD_RUNNING)) {
			next_test = all_threads[idx];
			break;
		}
		idx = (idx+1)%UTHREAD_MAX_THREADS;
	}
	next = get_next_running(current);
	assert(next);
	assert(next == next_test);
	assert(next == all_threads[next->id]);
	//int cc = sprintf(c,"Calling switch from alarm\n");
	//PRK(1,c,cc);
	context_switch(prev,next);

	return;
}

void reset_alarm() {
//	printf("resetting alarm for %d, ualarming: %d\n",current->id,UTHREAD_TIME_SLICE * current->prio);
	assert(UTHREAD_TIME_SLICE * current->prio > 0);
	ualarm(UTHREAD_TIME_SLICE * current->prio,0);
}

void activate_thread(uthread thread) {
	thread->state = UTHREAD_RUNNING;
}

void deactivate_thread(uthread thread) {
	thread->state = UTHREAD_SUSPENDED;
}
void deactivate_thread_and_cs(uthread thread) {
	assert(thread);
	deactivate_thread(thread);
	find_next_and_cs(thread);
}

void find_next_and_cs(uthread thread) {
	uthread next = get_next_running(thread);
	PRK(1,"A\n",2);
	while (!next) {
		sched_yield(); /* deadlock! */
		assert(thread);
		next = get_next_running(thread);
	}
	PRK(1,"B\n",2);
	context_switch(thread,next);
}

void garbage_collector() {
	uthread_id i;
	char c[200];
	int ret;
	for (i = 0 ; i < UTHREAD_MAX_THREADS; i++) {
		if (all_threads[i] && all_threads[i]->state == UTHREAD_DELETED) {
			assert(i != 0);
			ret = sprintf(c,"current->id = %d, i = %d, stack: 0x%x\n",current->id,i,all_threads[i]->stack);
			PRK(1,c,ret);
			free(all_threads[i]->stack);
//			PRK(1,"J\n",2);
			// TODO: free mutexs and io whatever needed
			free(all_threads[i]);
//			PRK(1,"I\n",2);
			all_threads[i] = NULL;
		}
	}
//	PRK(1,"G\n",2);
}
int uthread_cond_init() {
	if (!is_uthread_initialized){
		if (uthread_init() == UTHREAD_FAIL){
			return UTHREAD_FAIL;
		}
	}
}
